#include "heapsort.h"

// topk问题
// 问题要求给你一个很大量的数据,让你仅使用少量内存的情况下,对数据进行排序,得出数据的前k位最大或者最小数据
// 假设我们需要给n个数据排序,常规的排序方法都是需要把数据加载进内存里面进行使用,这样就会消耗大量的内容空间
// 但是利用硬盘的空间,就可以在不消耗内存过多空间的情况下读取全部数据了
// 使用文件指针变量对文件里面的数据依次进行读取操作,就可以在不过多消耗内存的情况下进行排序了
// 在排序的过程中,我们可以利用堆排序的特性进行筛选数据,就可以在实现空间复杂度低的情况下进行较快的排序筛选,找到我们想要的数据了

// 操作步骤如下:
// 1.根据我们需要的数据多少(k),在内存中动态申请一块能存放k个数据的空间
// 2.读取文件,将文件中前k位数据依次写进内存区域里面
// 3.将区域进行向下调整算法,使其变成一个类似于堆结构的存放顺序
// 这时候,由于堆的特点,该区域的头数据为整块区域数据的极值,之后的数据与该数据进行比对即可确定是否比区域内数据大或小
// 4.在排序好之后,我们将剩余(k - n)个数据依次和头数据进行比对,根据条件判断是否将该数据与头数据进行替换
// 5.替换之后进行向下调整算法,直到所有数据比对完成
// 这时候我们就找到了最大或最小的k位数据了

// 注意:
// 根据所求的数据是最大还是最小的,我们需要改变建堆是大堆或者小堆
// 在比较的数据时,需要根据求的数据最大还是最小,改变交换条件

void CreateNDate ()
{
	
	// 造数据
	
	int n = 10000 ;

	srand(time (0)) ;

	const char* file = "data.txt" ;
	
	FILE* fin = fopen(file, "w") ;

	if (fin == NULL)
	{
		
		perror("fopen error") ;
		
		return ;

	}

	for (size_t i = 0; i < n; ++i)
	{

		int x = rand() % 1000000 ; // 随机范围在0 ~ 1000000之间

		fprintf(fin, "%d\n", x) ; // 写入进文件里面

	}

	fclose(fin) ;

}

void Swap (int* x , int* y)
{

    int tmp = *x ;

    *x = *y ;

    *y = tmp ;

}

void AdjustDown (int* arr , int parent , int n)
{

    int child = parent * 2 + 1 ; // 左孩子

    while (child < n)
    {

        // 建大堆: <
        // 建小堆: >

        if (child + 1 < n && arr [child] > arr [child + 1])
        {

            child++ ;

        }

        // 建大堆: <
        // 建小堆: >

        if (arr [parent] > arr [child])
        {

            Swap (&arr [child] , &arr [parent]) ;

            parent = child ;

            child = parent * 2 + 1 ;

        }

        else
        {

            break ;

        }

    }

}

// TopK排序并打印数据

void PrintTopK (int k)
{

	// 找最大的前k个数据: 建小堆
	// 如果找最小的前k个数据: 建大堆

	int* minHeap = (int*) malloc (sizeof (int) * k) ;

	if (minHeap == NULL)
	{

		perror ("malloc faild!") ;

		exit (1) ;

	}

	FILE* fout = fopen ("data.txt" , "r") ;

	if (fout == NULL)
	{

		perror ("fopen fail!") ;

		exit (2) ;

	}

	for (int i = 0 ; i < k ; i++)
	{

		fscanf (fout , "%d" , &minHeap [i]) ;

	}

	// minHeap -- 向下调整建堆

	for (int i = (k - 1 - 1) / 2 ; i >= 0 ; i--) // 将得到的数组排序成堆
	{

		AdjustDown (minHeap , i , k) ;

	}

	// 遍历剩下的n - k个数据,跟堆顶比较,满足条件就替换堆顶

	int x = 0 ;

	while (fscanf (fout , "%d" , &x) != EOF)
	{

		// x minHeap-top
		// 最小: <
		// 最大: >

		if (x > minHeap [0])
		{

			minHeap [0] = x ;

			AdjustDown (minHeap , 0 , k) ;

		}

	}

	// 由于堆头数据为极值,根据大小堆的区分,这个极值是最大或者最小值
	// 如果想要求最大k的数据的话,我们就需要建小堆,将每次数据大于堆头的数据进行入堆并排序
	// 如果想求最小k的数据的话,我们就需要建小堆,将每次数据小于堆头的数据进行入堆并排序

    int size = k - 1 ;

	while (size)
    {

        Swap (&minHeap [0] , &minHeap [size]) ;

        AdjustDown (minHeap , 0 , size) ;

        size-- ;

    }
    

    for (int i = 0 ; i < k ; i++)
    {

        printf ("%d " , minHeap [i]) ;

    }

	fclose (fout) ;

	fout = NULL ;

	free (minHeap) ;

	minHeap = NULl ;

}